<?php


class Solution {

    /**
     * @param String $s
     * @return String[][]
     */
    function partition($s) {//深度优先遍历
        $sLen=strlen($s);
        if($sLen==0)//递归结束
            return [];

        $ret=[];//保存返回结果
        for($i=1;$i<=$sLen;$i++){
            $subStr=substr($s,0,$i);
            if($this->isPartition($subStr)){
                $subArr=$this->partition(substr($s,$i,$sLen-$i));//回溯
                foreach($subArr as $v){
                    array_unshift($v,$subStr);
                    $ret[]=$v;//符合条件存入
                }
                if(empty($subArr)){//递归到底返回
                    $ret[]=[$subStr];//符合条件存入，因为前面已经判断过是回文串
                }
            }
        }

        return $ret;
    }

    //判断字符串是否是回文串
    function isPartition($s){
        $sLen=strlen($s);
        $l=0;
        $r=$sLen-1;
        while($l<$r){
            if($s[$l]!=$s[$r])
                return false;
            $l++;
            $r--;
        }
        return true;
    }
}

?>